import java.util.HashMap;

/**
 * @description:
 * @Author: wuzhenbin
 * @CreateTime: 2025-02-12
 */
public class leetcode_560 {
    public static void main(String[] args) {
        System.out.println(subarraySum1(new int[]{1,1,1}, 2));
    }

//    public static int subarraySum(int[] nums, int k) {
//        int res = 0;
//        int left = 0;
//        while (left < nums.length) {
//            int tmp = nums[left];
//            if(tmp==k&&tmp!=0){
//                left++;
//                res++;
//                continue;
//            }
//            else if(tmp==0&&k==0)res++;
//            int i = left + 1;
//            while (i < nums.length) {
//                tmp += nums[i++];
//                if ((k - tmp) == 0) res++;
//            }
//
//            left++;
//        }
//        return res;
//
//    }

    public static int subarraySum(int[] nums, int k) {
        HashMap<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1);  // 初始化：前缀和为0的子数组出现次数为1
        int currentSum = 0;
        int result = 0;

        for (int num : nums) {
            currentSum += num;  // 计算当前前缀和

            // 如果当前前缀和减去k的值在哈希表中存在，说明找到一个符合条件的子数组
            if (prefixSumCount.containsKey(currentSum - k)) {
                result += prefixSumCount.get(currentSum - k);
            }

            // 将当前前缀和加入哈希表，更新其出现次数
            prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
        }

        return result;
    }
    public static int subarraySum1(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        //这个非常重要
        map.put(0, 1);
        int res=0;
        int prefixSum=0;
        for (int num : nums) {
            prefixSum+=num;
            if(map.containsKey(prefixSum-k)){
                res+=map.get(prefixSum-k);
            }
            Integer orDefault = map.getOrDefault(prefixSum, 0);
            map.put(prefixSum,orDefault+1);
        }

        return res;
    }

}